package com.lwg.datastructure.basicDataStructureDemo;


import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Tree {
    
    // 前序遍历 A→B→D→E→C→F
    public void preorderTraversal(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 将根节点入栈
        stack.push(treeNode);
        while (!stack.isEmpty()) {
            // 判断是否有左右节点，现将根节点出栈，再将左右节点入栈，
            // 栈是先入后出，所以前序遍历是先入右节点，再入左节点
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        
    }
    
    // 中序遍历 左->根->右
    public void middorderTraversal(TreeNode treeNode) {
        Stack<TreeNode> stack = new Stack<>();
        if (treeNode == null) {
            return;
        }
        while (treeNode != null || !stack.isEmpty()) {
            while (treeNode != null) {
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            stack.pop();
            treeNode = treeNode.right;
        }
    }
    
    // 后续遍历 左->右->根
    public static void postOrder(TreeNode tree) {
        if (tree == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        
        stack1.push(tree);
        
        while (!stack1.isEmpty()) {
            TreeNode treeNode = stack1.pop();
            stack2.push(treeNode);
            if (treeNode.left != null) {
                stack1.push(treeNode);
            }
            if (tree.right != null) {
                stack1.push(treeNode);
            }
        }
    }
    
    // BFS 宽度优先搜索 又称 广度优先搜索
    public static void levelOrder(TreeNode tree) {
        if (tree == null) {
            return;
        }
        LinkedList<TreeNode> list = new LinkedList<>();  //链表相当于栈
        list.add(tree);
        
        while (!list.isEmpty()) {
            TreeNode treeNode = list.poll();  //移除链表的头部
            System.out.println(treeNode.value);
            if (treeNode.left!=null){
                list.add(treeNode.left);
            }
            if (treeNode.right!=null){
                list.add(treeNode.right);
            }
        }
    }
    
    // DFS深度优先遍历  A→B→D→E→C→F
    
    
}

class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode() {
    }
    
    public TreeNode(int value) {
        this.value = value;
    }
    
    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}